Assistants: (see Piazza for hours and contact info)
GTA: Petar Duric
GTA: Yong Li
UTA: Nathaniel Lopez
UTA: Azka Saquib
Prerequisites:
CS211 and MATH125 (C or better in both)
Textbook:
Hamburger and Richards,
Logic and Language Models for Computer Science,
Fourth Edition
Other requirements:
A scanner, camera, or digital drawing tool to use to prepare digital uploads of homework
Lectures: Lectures will be held in-person; Supporting videos will be available via Blackboard.
Course resources:
Piazza for questions and discussion. Please note that while Piazza requests donations, it is due to Piazza's business model independent from any input from the university; students should not feel any obligation to provide donations.
Blackboard to view grades and course materials.
GradeScope for exam feedback, quizzes, and homework assignment turn-in/feedback.
Schedule: see below for schedule; subject to change.
Description
This course is an introduction to two kinds of formal systems - languages and logics - with important applications to computer science. The study of formal languages underlies important aspects of compilers and other language processing systems, as well as the theory of computation. Various systems of logic and automatic reasoning are put to use in artificial intelligence, database theory and software engineering. The entire course will give you practice in precise thinking and proof methods that play a role in the analysis of algorithms. The programming assignments provide practical experience with some theoretical topics.
Outcomes
| Grade | A+ | A | A- | B+ | B | B- | C+ | C | C- | D | F |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Min Score | 98 | 92 | 90 | 88 | 82 | 80 | 78 | 72 | 70 | 60 | ↓ |
It is a departmental requirement that all undergraduate Computer Science students taking CS330 must speak with their faculty advisor during the semester and submit an advising form (found here) documenting their visit.
All graded work in this class is individual. Any direct contribution on an exam, quiz, or assignment will be treated as a violation of George Mason's Honor Code and the CS Department Honor Code, and will typically result in failing the class.
The use of AI tools (including but not limited to ChatGPT) to aid in the completion of graded assignments/quizzes/exams, and the use of solutions which are derived directly or indirectly from AI prompts, is considered unauthorized assistance and is prohibited under the honor code.
Some kinds of participation in third-party online study sites violate the GMU Honor code: these include accessing questions for this class which have been uploaded by others; accessing exam or assignment answers for this class; uploading of any of the instructor's materials or exams; and uploading any of your own answers or finished work. It is your resposibility to protect your work, including protecting your computer with a password and avoiding sites which make your work publicly visible. Always consult with the professor before using these sites.
Please respect the importance of upholding the Honor Code, since it affects the meaningfulness of your degree and the degrees of other students. As a practical matter, an understanding of the material presented in this course has a potential to positively impact your ability to acquire computing skills and perform computing skill which will be used in your future careers; you put yourself in the best position to gain that understanding when you rely on your own work.
Privacy statment
All course materials posted to Blackboard or other course site are private to this class; by federal law, any materials that identify specific students (via their name, voice, or image) must not be shared with anyone not enrolled in this class. In the event that any class meetings need to be held synchronously online, those classes will be recorded to provide necessary information for students in this class. Recordings will be stored on Blackboard and will only be accessible to students taking this course during this semester.
Disability accomodations
Disability Services at George Mason University is committed to providing equitable access
to learning opportunities for all students by upholding the laws that ensure equal treatment
of people with disabilities. Students seeking accommodations for this class, please first
visit Disability Services (ods@gmu.edu;
703-993-2474) for detailed information about the
Disability Services registration process. Then please discuss the approved accommodations with
the instructor. The Disability Services office can be found in Student Union Building I (SUB I),
Suite 2500.
Diversity and inclusion
George Mason University promotes a diverse, inclusive, and anti-racist environment, under the belief that a just and equitable learning environment is a strong learning environment. Students are valued as individuals, irrespective of differences in race, ethnicity, national origin, first language, economic status, gender, gender expression and identity, sexual orientation, religion, disability, or age. As an important member of the GMU community, the Department of Computer Science is integral to the goal of cultivating an environemnt which is committed to inclusion and anti-racism.
Students who prefer to be addressed by a specific name or gender pronouns should share this information with the instructor (he/him). Additionally, name and pronouns can be changed in the GMU records.
Title IX
As a faculty member and designated "Responsible Employee," I am required to report all disclosures of sexual assault, interpersonal violence, and stalking to Mason's Title IX Coordinator, per university policy 1412.
Students who wish to speak with someone confidentially should contact the Student Support and Advocacy Center (ssac@gmu.edu; 703-993-3686) or Counseling and Psychological Services (caps@gmu.edu; 703-993-2380). Assistance may also be sought from GMU's Title IX Coordinator (titleix@gmu.edu; 703-993-8730).
COVID-19
This class is in person during the current semester. For information regarding the virus and current university policy regarding the virus, consult the Safe Return to Campus page.
Schedule
| Week | Date | Topic | Assignments/Notes |
|---|---|---|---|
| Week 1 | Jan 14-20 | Introduction; Mathematical Preliminaries, Sections 1.1-1.6. Propositional Logic, Sections 2.1-2.7. | |
| Jan 15 | |||
| Jan 16 | Introduction; Mathematical Preliminaries | ||
| Jan 17 | |||
| Jan 18 | Propositional Logic | Practice HW 2.4, 2.7a, 2.8, 2.9, 2.11 | |
| Jan 19 | Turn-in HW 1 (Prop Logic) assigned | ||
| Week 2 | Jan 21-27 | Proofs by Deduction, Sections 3.1-3.9. | |
| Jan 22 | |||
| Jan 23 | Propositional Logic review | Quiz 1 (Intro/Prop Logic) opens | |
| Jan 24 | Turn-in HW 1 (Prop Logic) due | ||
| Jan 25 | Proof by Deduction | Practice HW 3.10 (1st-4th), Prove Transitive/Contrapositive/Trivial/Vacuous/Alt Elim/Contradiction Elim, 3.8 | |
| Jan 26 | Quiz 1 (Intro/Prop Logic) closes; Turn-in HW 2 (Deduction) assigned | ||
| Week 3 | Jan 28-Feb 3 | Predicate Logic, Sections 4.1-4.5. | |
| Jan 29 | |||
| Jan 30 | Proof by Deduction review | Quiz 2 (Deduction) opens | |
| Jan 31 | Turn-in HW 2 (Deduction) due | ||
| Feb 1 | Predicate Logic | Practice HW 4.1, 4.3, 4.7, 4.10a,b | |
| Feb 2 | Quiz 2 (Deduction) closes; Turn-in HW 3 (Pred Logic) assigned | ||
| Week 4 | Feb 4-10 | Mathematical Induction, Sections 5.1-5.5. | |
| Feb 5 | |||
| Feb 6 | Predicate Logic review | Quiz 3 (Pred Logic) opens | |
| Feb 7 | Turn-in HW 3 (Pred Logic) due | ||
| Feb 8 | Mathematical Induction | Practice HW 5.2-5.4, 5.9 | |
| Feb 9 | Quiz 3 (Pred Logic) closes; Turn-in HW 4 (Induction) assigned | ||
| Week 5 | Feb 11-17 | Program Verification, Sections 6.1-6.4. | |
| Feb 12 | |||
| Feb 13 | Mathematical Induction review | Quiz 4 (Induction) opens | |
| Feb 14 | Turn-in HW 4 (Induction) due | ||
| Feb 15 | Program Verification | Practice HW 6.2-6.4, 6.6, 6.7 | |
| Feb 16 | Quiz 4 (Induction) closes; Turn-in HW 5 (Prog Verif) assigned | ||
| Week 6 | Feb 18-24 | Midterm warm-up. | |
| Feb 19 | |||
| Feb 20 | Program Verification review | Quiz 5 (Prog Verif) opens | |
| Feb 21 | Turn-in HW 5 (Prog Verif) due | ||
| Feb 22 | Midterm warm-up | Midterm covers material from chapters 1-6 | |
| Feb 23 | Quiz 5 (Prog Verif) closes | ||
| Week 7 | Feb 25-Mar 2 | Midterm Exam. Language Basics; Regular Languages, Chapter 7 + Sections 8.1-8.2 | .|
| Feb 26 | |||
| Feb 27 | Midterm Exam | ||
| Feb 28 | |||
| Feb 29 | Language Basics/Regular Languages | Practice HW 7.4, 7.5, 7.12, 7.15, 8.2, 8.3, 8.5, 8.6 | |
| Mar 1 | Turn-in HW 6 (Langs/RLs) assigned | ||
| Week 8 | Mar 3-9 | Spring Break | |
| Mar 4 | |||
| Mar 5 | No Class | ||
| Mar 6 | |||
| Mar 7 | No Class | ||
| Mar 8 | |||
| Week 9 | Mar 10-16 | Regular Expressions/Regular Grammars, Sections 8.2-8.5 | |
| Mar 11 | |||
| Mar 12 | Language Basics/Regular Languages review | Quiz 6 (Langs/RLs) opens | |
| Mar 13 | Turn-in HW 6 (Langs/RLs) due | ||
| Mar 14 | Regular Expressions/Regular Grammars | Practice HW 8.8, 8.9, 8.11, 8.12 | |
| Mar 15 | Quiz 6 (Langs/RLs) closes; Turn-in HW 7 (REs/RGs) assigned | ||
| Week 10 | Mar 17-23 | Regular Grammar Conversions, Sections 8.5,8.6 | |
| Mar 18 | |||
| Mar 19 | Regular Expressions/Regular Grammars review | Quiz 7 (REs/RGs) opens | |
| Mar 20 | Turn-in HW 7 (REs/RGs) due | ||
| Mar 21 | Regular Grammar Conversion | Practice HW 8.14, 8.15 | |
| Mar 22 | Quiz 7 (REs/RGs) closes; Turn-in HW 8 (RG Conv) assigned | ||
| Week 11 | Mar 24-30 | Finite Automata, Sections 9.1-9.4,9.8 | |
| Mar 25 | |||
| Mar 26 | Regular Grammar Conversion review | Quiz 8 (RG Conv) opens | |
| Mar 27 | Turn-in HW 8 (RG Conv) due | ||
| Mar 28 | Finite Automata | Practice HW 9.7, 9.5, 9.16, 9.17 | |
| Mar 29 | Quiz 8 (RG Conv) closes; Turn-in HW 9 (FA) assigned | ||
| Week 12 | Mar 31-Apr 6 | Nondeterministic Finite Automata/Properties of Regular Languages, Sections 9.5-9.7 | |
| Apr 1 | |||
| Apr 2 | Finite Automata review | Quiz 9 (FA) opens | |
| Apr 3 | Turn-in HW 9 (FA) due | ||
| Apr 4 | Nondeterministic Finite Automata/Properties of Regular Languages | Practice HW 9.8, 9.9, 9.25 | |
| Apr 5 | Quiz 9 (FA) closes; Turn-in HW 10 (NFA/Prop RLs) assigned | ||
| Week 13 | Apr 7-13 | Context-Free Grammars, Sections 10.1-10.4 | |
| Apr 8 | |||
| Apr 9 | Nondeterministic Finite Automata/Properties of Regular Languages review | Quiz 10 (NFA/Prop RLs) opens | |
| Apr 10 | Turn-in HW 10 (NFA/Prop RLs) due | ||
| Apr 11 | Context-Free Grammars | Practice HW 10.1, 10.2, 10.8 | |
| Apr 12 | Quiz 10 (NFA/Prop RLs) closes; Turn-in HW 11 (CFGs) assigned | ||
| Week 14 | Apr 14-20 | Pushdown Automata/Turing Machines, Sections 11.1,11.2, 12.2 | |
| Apr 15 | |||
| Apr 16 | Context-Free Grammars review | Quiz 11 (CFGs) opens | |
| Apr 17 | Turn-in HW 11 (CFGs) due | ||
| Apr 18 | Pushdown Automata/Turing Machines | Practice HW 11.1, 11.4, 11.6, 11.9a (NPDA are allowed) | |
| Apr 19 | Quiz 11 (CFGs) closes | ||
| Week 15 | Apr 21-27 | Final Exam warm-up | |
| Apr 22 | |||
| Apr 23 | Pushdown Automata/Turing Machines review | Quiz 12 (PDA/TMs) opens | |
| Apr 24 | |||
| Apr 25 | Final Exam warm-up | Final covers material from chapters 7-12 | |
| Apr 26 | Quiz 12 (PDA/TMs) closes | ||
| exam week | May 1-8 | Reading Days Apr 30 and May 5 | |
| May 2 (Thu) | Final Exam Section 002 | 7:30-10:15am Sec 002 | |
| May 7 (Tue) | Final Exam Section 005 | 10:30am-1:15pm Sec 005 |